
//
// Created by Administrator on 2021/11/15.
// May Saint Diana bless you!
//
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxDistance(vector<int> &nums1, vector<int> &nums2) {
        // 有效距离：i <= j 且 nums1[i] <= nums2[j] 的j-i
        // 对于每个i，需要在nums2中，[i,len(nums2)]之内找到第一个比nums1[i]小的数字, nums2[j-1]就是最后一个大等于它的
        int ans = 0;
        unsigned int m = nums1.size(), n = nums2.size();
        for (int i = 0; i < m; ++i) {
            int j = upper_bound(nums2.begin(), nums2.end(), nums1[i], greater<>()) - nums2.begin(); // 小于
            if (j > 0) {
                ans = max(ans, j - 1 - i); // nums2[j-1]是第一个大等于nums1[i]的
            }
        }
        return ans;
    }

    /**
     * 假设下标 j 对应的最小下标为 i，当 jj 变为 j+1 时，由于 nums2非递增，即 nums2[j]≥nums2[j+1]，
     * 那么 nums1中可取元素的上界不会增加。同时由于nums1也非递增，因此 j+1 对应的最小下标 i'定满足 i′≥i
     * 也就是说，i的范围是一定越来越小的
     * @param nums1
     * @param nums2
     * @return
     */
    int maxDistance2(vector<int> &nums1, vector<int> &nums2) {
        size_t n1 = nums1.size();
        size_t n2 = nums2.size();
        int i = 0;
        int ans = 0;
        for (int j = 0; j < n2; ++j) {
            while (i < n1 && nums1[i] > nums2[j]) {
                ++i;
            }
            if (i < n1) {
                ans = max(ans, j - i);
            }
        }
        return ans;
    }
};

int main() {
    vector<int> nums1{55, 30, 5, 4, 2};
    vector<int> nums2{100, 20, 10, 10, 5};
    Solution solution;
    cout << solution.maxDistance(nums1, nums2) << endl;
    return 0;
}


